{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/path-sum-ii\n",
    "\n",
    "\n",
    "\n",
    "Runtime: 20 ms, faster than 40.60% of C++ online submissions for Path Sum II.\n",
    "Memory Usage: 41 MB, less than 5.56% of C++ online submissions for Path Sum II.\n",
    "\n",
    "\n",
    "\n",
    "```cpp\n",
    "#include <iostream>\n",
    "#include <ctime>\n",
    "#include <vector>\n",
    "#include<numeric>\n",
    "\n",
    "using namespace std;\n",
    "\n",
    "struct TreeNode\n",
    "{\n",
    "    int val;\n",
    "    TreeNode *left;\n",
    "    TreeNode *right;\n",
    "    TreeNode() : val(0), left(nullptr), right(nullptr) {}\n",
    "    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n",
    "    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n",
    "};\n",
    "\n",
    "class Solution\n",
    "{\n",
    "public:\n",
    "    vector<vector<int>> paths;\n",
    "    int target;\n",
    "\n",
    "    vector<vector<int>> pathSum(TreeNode *root, int sum)\n",
    "    {\n",
    "        this->paths = {};\n",
    "        this->target = sum;\n",
    "        this->travel(root, vector<int>());\n",
    "        return this->paths;\n",
    "    }\n",
    "\n",
    "    void travel(TreeNode *node, vector<int> l) {\n",
    "        if (node == nullptr) {\n",
    "            return;\n",
    "        } else {\n",
    "            l.push_back(node->val);\n",
    "            if ((node->left == nullptr) && (node->right == nullptr)) {\n",
    "                if (accumulate(l.begin(),l.end(),0) == this->target) {\n",
    "                    this->paths.push_back(vector<int>(l.begin(), l.end()));\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        int length = l.size();\n",
    "        this->travel(node->left, vector<int>(l.begin(), l.end()));\n",
    "        this->travel(node->right, vector<int>(l.begin(), l.begin()+length));\n",
    "    }\n",
    "};\n",
    "\n",
    "int main(int argc, char *argv[])\n",
    "{\n",
    "    auto s = Solution();\n",
    "    TreeNode root = TreeNode(0);\n",
    "    TreeNode a = TreeNode(1);\n",
    "    TreeNode b = TreeNode(2);\n",
    "    root.left = &a;\n",
    "    root.right = &b;\n",
    "    auto r = s.pathSum(&root, 1);\n",
    "    cout << \"result: \" << r.size() << endl;\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}